/*************************************************************************
	> File Name: P1865.cpp
	> Author: yufangze
	> Mail: 2224590123@qq.com
	> Created Time: 2025-04-23 17:57:24
 ************************************************************************/

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_N 1000000
bool prime[MAX_N + 5];
int sum[MAX_N + 5];

void init_prime() {
    prime[1] = true;
    for (int i = 2; i <= MAX_N; i++) {
        if (prime[i]) continue;
        for (int j = i, I = MAX_N / i; j <= I; j++) {
            prime[i * j] = 1;
        }
    }
    return ;
}

int main() {
    init_prime();
    for (int i = 1; i <= MAX_N; i++) {
        sum[i] = sum[i - 1] + !prime[i];
    }
    int n, m;
    cin >> n >> m;
    while (n--) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l < 1 || l > m || r < 1 || r > m) {
            printf("Crossing the line\n");
        } else {
            int val = sum[r] - sum[l - 1];
            printf("%d\n", val);
        }
    }
    return 0;
}
